//
//  ViewController.swift
//  CodeList
//
//  Created by 山神 on 2021/9/4.
//

import UIKit

class ViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
        let _ = LinDemo()
    }
}

//栈练习
extension ViewController {
    //    有效的字符串
    func isValid(string: String) -> Bool {
        if string.count == 0  { return false }
        var stack: [String] = []
        let dict = ["(": ")","[": "]","{": "}"]

        for c in string {
            if dict.keys.contains(c.description) {
                stack.append(c.description) //如果是左括号就入栈
            } else {
                if !stack.isEmpty && c.description == dict[stack.last!] { //如果是右括号，并且匹配就出栈
                    stack.removeLast()
                } else {
                    return false
                }
            }
        }
        return stack.count == 0
    }
}

//二叉树
extension ViewController {
    func searchErcha() {
        let arr = [3,9,20,nil,nil,15,7]

    }
}

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

class Solution {
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        guard root != nil else { return [] }
        var queue = [TreeNode]()
        var res = [[Int]]()
        queue.append(root!)
        while !queue.isEmpty {
            let size = queue.count
            var level = [Int]() //存放该层所有数值
            for _ in 0 ..< size {
                let node = queue.removeFirst()
                level.append(node.val)
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
            }
            res.append(level)
        }
        return res
    }

    //前序遍历  根节点 -> 左节点 -> 右节点
    func preOrder(_ root: TreeNode?) -> Void {
        guard root != nil else { return }
        print("\(root!.val)\t", terminator: "")
        preOrder(root!.left)
        preOrder(root!.right)
    }

    //中序遍历 左节点 -> 根节点 -> 右节点
    func midOrder(_ root: TreeNode?) -> Void {
        guard root != nil else { return }
        midOrder(root!.left)
        print("\(root!.val)\t", terminator: "")
        midOrder(root!.right)
    }

    //后续遍历  左节点  -> 右节点 -> 根节点
    func afterOrder(_ root: TreeNode?) -> Void {
        guard root != nil else { return }
        afterOrder(root!.left)
        afterOrder(root!.right)
        print("\(root!.val)\t", terminator: "")
    }
}

//翻转二叉树
class Tree {
    var key: Int   //节点上显示的关键值
    var leftTree: Tree?  //左子树
    var rightTree: Tree? //右子树

    //初始化方法
    init(key: Int) {
        self.key = key
    }

    func invertBinaryTreeWithRecursive(root: Tree) {
        //1
        let tempT = root.leftTree
        root.leftTree = root.rightTree
        root.rightTree = tempT

        //2
        if let leftT = root.leftTree {
            //递归调用
            invertBinaryTreeWithRecursive(root: leftT)
        }
        if let rightT = root.rightTree {
            invertBinaryTreeWithRecursive(root: rightT)
        }
    }
}


